home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / util / cli / UnixUtils.lha / UnixUtils / Source / btree.c next >
Encoding:
C/C++ Source or Header  |  1992-03-25  |  5.5 KB  |  263 lines
  1. /*------------------------------------------------*
  2.  | File: btree.c - Binary tree routines for sort. |
  3.  | v1.00 MLO 911226 - see the comments in sort.c  |
  4.  *------------------------------------------------*/
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include "mlo.h"
  10. #include "sort.h"
  11.  
  12. extern short int abortProg;
  13. extern Boolean reverse;
  14. extern FILE *fp;
  15. extern Node *root;
  16.  
  17. #ifndef SIMPLE
  18. extern char *temp1;
  19. #endif
  20.  
  21. #ifdef BALANCED_TREE
  22. extern Node *critical, *father;
  23. static short int sign(int x);
  24. #endif
  25.  
  26. void FreeTree(
  27.   Node *pN
  28. ){
  29.  
  30. /**
  31.  | Frees (recursively) the binary tree, at node pointed to by pN.
  32. **/
  33.  
  34.   if (pN->left != NULL)   FreeTree(pN->left);
  35.   if (pN->right != NULL)  FreeTree(pN->right);
  36.   free(pN);
  37. }
  38.  
  39. Node *InsertTree(
  40.   char *buffer,
  41.   Node *pN
  42. ){
  43.  
  44. /**
  45.  | Inserts (recursively) the string "buffer" in the binary tree; see
  46.  | the comments in sort.c about the balanced binary tree algorithm.
  47. **/
  48.  
  49. #ifdef BALANCED_TREE
  50.  
  51.   if (pN != NULL) {
  52.  
  53. /**
  54.  | This node is not empty; compare our string with the one
  55.  | related to this node, and follow right or left branch -
  56.  | or bump the node counter if the strings are identical (if
  57.  | so, the tree is already balanced since no new nodes has been
  58.  | created; if not, alter the balance count in this node toward
  59.  | right or left). For the balancing algorithm, we need to know
  60.  | the last node having a non-zero balance factor, and his father.
  61. **/
  62.     short int z;
  63.  
  64.     if ((z = Compare(buffer, pN->line)) == 0) {
  65.       (pN->count)++;
  66.       critical = NULL;
  67.     } else {
  68.       if (pN->balance)    critical = pN;
  69.       if (z < 0) {
  70.         if (pN->left != NULL   &&   pN->left->balance)    father = pN;
  71.         pN->left = InsertTree(buffer, pN->left);
  72.       } else {
  73.         if (pN->right != NULL   &&   pN->right->balance)  father = pN;
  74.         pN->right = InsertTree(buffer, pN->right);
  75.       }
  76.     }
  77.   } else {
  78.  
  79. /**
  80.  | We are at the end of the binary tree; a new node
  81.  | must be inserted here.
  82. **/
  83.  
  84.     if ((pN = malloc(sizeof(Node)+strlen(buffer))) == NULL) {
  85.       puts("sort: couldn't obtain heap memory.");
  86.       FreeTree(root);
  87.       if (temp1 != NULL) free(temp1);
  88.       if (fp != NULL) fclose(fp);
  89.       exit(SYS_ABORT_CODE);
  90.     }
  91.     strcpy(pN->line, buffer);
  92.     pN->balance = 0;
  93.     pN->count   = 1;
  94.     pN->left    = NULL;
  95.     pN->right   = NULL;
  96.   }
  97.   return pN;
  98.  
  99. #else
  100.  
  101. /**
  102.  | Unbalanced binary tree algorithm.
  103. **/
  104.  
  105.   if (pN != NULL) {
  106.     short int z;
  107.  
  108. #ifdef SIMPLE
  109.     if ((z = strcmp(buffer, pN->line)) == 0) {
  110. #else
  111.     if ((z = Compare(buffer, pN->line)) == 0) {
  112. #endif
  113.  
  114.       (pN->count)++;
  115.     } else if (z < 0) {
  116.       pN->left = InsertTree(buffer, pN->left);
  117.     } else {
  118.       pN->right = InsertTree(buffer, pN->right);
  119.     }
  120.   } else {
  121.     if ((pN = malloc(sizeof(Node)+strlen(buffer))) == NULL) {
  122.       puts("sort: couldn't obtain heap memory.");
  123.       FreeTree(root);
  124.  
  125. #ifndef SIMPLE
  126.       if (temp1 != NULL) free(temp1);
  127. #endif
  128.  
  129.       if (fp != NULL) fclose(fp);
  130.       exit(SYS_ABORT_CODE);
  131.     }
  132.     strcpy(pN->line, buffer);
  133.     pN->count = 1;
  134.     pN->left  = NULL;
  135.     pN->right = NULL;
  136.   }
  137.   return pN;
  138.  
  139. #endif
  140. }
  141.  
  142. void PrintTree(
  143.   Node *pN
  144. ){
  145.  
  146. /**
  147.  | Prints (recursively) the binary tree, at node pointed to by pN.
  148.  | The allocated memory is also freed.
  149. **/
  150.  
  151.   if (reverse) {
  152.     if (pN->right != NULL) PrintTree(pN->right);
  153.   } else {
  154.     if (pN->left != NULL) PrintTree(pN->left);
  155.   }
  156.  
  157.   if (!abortProg) {
  158.     while ((pN->count)--) fputs(pN->line, stdout);
  159.     CheckBreak(False);
  160.   }
  161.  
  162.   if (reverse) {
  163.     if (pN->left != NULL) PrintTree(pN->left);
  164.   } else {
  165.     if (pN->right != NULL) PrintTree(pN->right);
  166.   }
  167.  
  168.   free(pN);
  169. }
  170.  
  171. #ifdef BALANCED_TREE
  172.  
  173. void BalanceTree(
  174.   char *key
  175. )
  176. {
  177.  
  178. /**
  179.  | If the binary tree needs re-balancing (critical != NULL),
  180.  | we rearrange the node ordering  so that the number of them
  181.  | being in the right sub-tree and in the left sub-tree in
  182.  | EVERY node differs at most by one. To obtain this, is
  183.  | sufficient to start from *critical.
  184. **/
  185.  
  186.   short int a, a0;
  187.   Node *p = critical;
  188.   Node *p0;
  189.  
  190.   if (critical == NULL) return;
  191.  
  192.   if ((a0 = Compare(key, p->line)) != 0) {
  193.     a0 = sign(a0);
  194.     p = p0 = (a0 > 0) ? p->right : p->left;
  195.     while ((a = Compare(key, p->line)) != 0) {
  196.       p->balance = (a = sign(a));
  197.       p = (a > 0) ? p->right : p->left;
  198.     }
  199.   }
  200.  
  201.   if (a0   &&   critical->balance == a0) {
  202.     if (p0->balance == a0) {
  203.       p = p0;
  204.       if (a0 > 0) {
  205.         critical->right = p0->left;
  206.         p0->left = critical;
  207.       } else {
  208.         critical->left = p0->right;
  209.         p0->right = critical;
  210.       }
  211.       critical->balance = p0->balance = 0;
  212.     } else if (p0->balance == -a0) {
  213.       if (a0 > 0) {
  214.         p = p0->left;
  215.         p0->left = p->right;
  216.         p->right = p0;
  217.         critical->right = p->left;
  218.         p->left = critical;
  219.       } else {
  220.         p = p0->right;
  221.         p0->right = p->left;
  222.         p->left = p0;
  223.         critical->left = p->right;
  224.         p->right = critical;
  225.       }
  226.       if (p->balance == 0) {
  227.         critical->balance = p0->balance = 0;
  228.       } else if (p->balance == a0) {
  229.         critical->balance = -a0;
  230.         p0->balance = 0;
  231.       } else if (p->balance == -a0) {
  232.         critical->balance = 0;
  233.         p0->balance = a0;
  234.       }
  235.       p->balance = 0;
  236.     }
  237.     if (father == NULL) {
  238.       root = p;
  239.     } else if (critical == father->right) {
  240.       father->right = p;
  241.     } else {
  242.       father->left = p;
  243.     }
  244.   } else {
  245.     critical->balance += a0;
  246.   }
  247. }
  248.  
  249. static short int sign(
  250.   int x
  251. ){
  252.  
  253. /**
  254.  | "sign" function
  255. **/
  256.  
  257.   if (x > 0)          return  1;
  258.     else if (x < 0)   return -1;
  259.     else              return  0;
  260. }
  261.  
  262. #endif
  263.